package datastructures;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.TreeSet;

import algorithms.Algo;

/**
 * @author Yuval Kesten
 *         <ul>
 *         My implementation of the Hash Tree Node
 *         </ul>
 */
public class HashTreeNode implements INode {

	public ItemSet set;
	public int depth;
	public HashMap<String, HashTreeNode> childrens;

	public HashTreeNode(int _depth) {
		childrens = new HashMap<String, HashTreeNode>();
		depth = _depth;
	}

	public boolean pruneAtDepth(double support, int numOfElements, int pruneDepth) {
		// A leaf
		if (childrens == null || childrens.isEmpty())
			return false;

		boolean alive = false;// There are still live itemsets of size
		// $pruneDepth

		Iterator<String> iter1 = childrens.keySet().iterator();
		HashTreeNode node;
		String key;

		// Prune or find the correct depth
		if (depth == pruneDepth - 1) {
			HashMap<String, HashTreeNode> frequentChilderens = null;
			frequentChilderens = new HashMap<String, HashTreeNode>();
			while (iter1.hasNext()) {
				key = iter1.next();
				node = childrens.get(key);
				if (pruneCondition(support, numOfElements, node)) {
					frequentChilderens.put(key, node);
					alive = true;
				}
			}
			childrens.clear();
			childrens = frequentChilderens;
		} else {
			while (iter1.hasNext()) {
				key = iter1.next();
				if (childrens.get(key).pruneAtDepth(support, numOfElements, pruneDepth))
					alive = true;
			}
		}
		return alive;
	}

	public boolean discoverAtDepth(double support, int numOfElements, int discoverDepth) {

		// A leaf
		if (childrens == null || childrens.isEmpty())
			return false;

		HashTreeNode node;
		ItemSet newIS;
		String key;
		boolean foundNewItemset = false;

		// Discover or find the correct depth
		if (depth == discoverDepth - 1) {

			TreeSet<String> sortedChildrensKeys = new TreeSet<String>();
			for (String child : childrens.keySet()) {
				sortedChildrensKeys.add(child);
			}

			Iterator<String> ascIter = sortedChildrensKeys.iterator();
			Iterator<String> desIter;
			String key1, key2;
			HashTreeNode node1, node2;
			HashTreeNode newNode;
			while (ascIter.hasNext()) {
				key1 = ascIter.next();
				node1 = childrens.get(key1);
				if (!isFrequent(support, numOfElements, node1))
					continue;
				desIter = sortedChildrensKeys.descendingIterator();
				while (desIter.hasNext()) {
					key2 = desIter.next();
					if (key2.equals(key1))
						break;
					node2 = childrens.get(key2);
					if (!isFrequent(support, numOfElements, node2))
						continue;

					foundNewItemset = true;
					Algo.incStats(discoverDepth + 1);

					// Two good candidates - merge them!
					newIS = new ItemSet();
					for (String item : node1.set) {
						newIS.addItem(item);
					}
					newIS.addItem(key2);// node2.set.getLast()==key2
					newNode = new HashTreeNode(discoverDepth + 1);
					newNode.set = newIS;
					node1.put(key2, newNode);
				}
			}
		} else {
			Iterator<String> iter1 = childrens.keySet().iterator();
			while (iter1.hasNext()) {
				key = iter1.next();
				node = childrens.get(key);
				// We don't discover not frequent subtrees
				// The null case is just for the root...
				if (node.set == null || isFrequent(support, numOfElements, node)) {
					if (childrens.get(key).discoverAtDepth(support, numOfElements, discoverDepth))
						foundNewItemset = true;
				}
			}
		}
		return foundNewItemset;
	}

	private boolean pruneCondition(double support, int numOfElements, HashTreeNode node) {
		return isFrequent(support, numOfElements, node);
	}

	private boolean isFrequent(double support, int numOfElements, HashTreeNode node) {
		return node.set.counter > (int) (support * numOfElements);
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		if (set != null)
			sb.append(set.toString());
		if (childrens != null) {
			for (Entry<String, HashTreeNode> entry : childrens.entrySet()) {
				sb.append(entry.getValue().toString());
			}
		}
		return sb.toString();
	}

	public void put(String key, HashTreeNode child) {
		childrens.put(key, child);
		// sortedChildrensKeys.add(key);
	}

	@Override
	public int getNumOfChildrens() {
		return childrens.size();
	}

	@Override
	public String toString(int support) {
		return toString();
	}

}
